/*
 * Copyright (C), 2015-2018
 * FileName: Solution066
 * Author:   zhao
 * Date:     2018/9/5 10:41
 * Description: 66题，加一
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredone;

/**
 * 〈一句话功能简述〉<br>
 * 〈66题，加一〉
 *
 * @author zhao
 * @date 2018/9/5 10:41
 * @since 1.0.1
 */
public class Solution066 {
  /**************************************
   * 题目
   给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

   最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。

   你可以假设除了整数 0 之外，这个整数不会以零开头。

   示例 1:

   输入: [1,2,3]
   输出: [1,2,4]
   解释: 输入数组表示数字 123。
   示例 2:

   输入: [4,3,2,1]
   输出: [4,3,2,2]
   解释: 输入数组表示数字 4321。
   **************************************/

  /**************************************
   *
   * 想法：
   *      判断digits为空
   *      主要是处理9进位的问题
   *      使用递归的方式
   * 我的做法：
   *      超过100%的测试案例
   *  总结：
   *      数组初始化，可以不需要进行拷贝
   *      在方法中对某个变量进行修改，原值不会修改
   * ***********************************/
  public int[] plusOne(int[] digits) {
    if (digits.length == 0) {
      return digits;
    }
    return plusByIndex(digits, digits.length - 1);
  }

  private int[] plusByIndex(int[] digits, int index) {
    // 判断9--》
    if (digits[index] == 9) {
      digits[index] = 0;

      if (index > 0) {
        // 往前循环
        return plusByIndex(digits, index - 1);
      } else {
        int[] ints = new int[digits.length + 1];
        ints[0] = 1;
        // 这里不需要拷贝，因为后面都是0
        //        System.arraycopy(digits, 0, ints, 1, digits.length)
        return ints;
      }
    } else {
      // 直接进行返回
      digits[index]++;
      return digits;
    }
  }

  /**************************************
   * 比我好的答案
   * ***********************************/
  public int[] better(int[] digits) {
    int len = digits.length;
    for (int i = len - 1; i > -1; i++) {
      if (digits[i] == 9) {
        digits[i] = 0;
      } else {
        digits[i]++;
        return digits;
      }
    }

    // 走到这里说明全部都是9
    int[] ints = new int[digits.length + 1];
    ints[0] = 1;
    return ints;

  }
}
